from typing import List


class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        m, n = len(nums1), len(nums2)
        dp = [[0 for _ in range(n + 1)] for __ in range(m + 1)]
        for i in range(1, m + 1):
            num1 = nums1[i - 1]
            for j in range(1, n + 1):
                num2 = nums2[j - 1]
                if num1 == num2:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

        return dp[-1][-1]


if __name__ == '__main__':
    sol = Solution()
    print(sol.maxUncrossedLines([1, 4, 2], [1, 2, 4]))
